package cn.lintcode;

import basic_class_01.Code_04_QuickSort;
import basic_class_01.Code_05_MergeSort;
import basic_class_01.Code_07_RadixSort;

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;


public class NumInFileSort {
    static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
//    static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

    private static List<Integer> getContext(String filepath) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(new FileInputStream("D:\\project\\java_web\\algorithm\\1.in")));
        int i = 0;
        ArrayList<Integer> list = new ArrayList<>();
        while (true){
            String s = reader.readLine();
            if (null == s ||
                    "".equals(s) ||
                    (i = Integer.valueOf(s).intValue()) == -1) {
                break;
            }
            list.add(i);
        }
        reader.close();
        return list;
    }

    private static void print(int[] list){
        StringBuilder stringBuilder = new StringBuilder();
        for (int k = 0; k < list.length; k++) {
            if (list[k] == 0) {
                continue;
            }
            stringBuilder.append(list[k]+"\n");
        }
//        list.stream().forEach(integer -> stringBuilder.append(integer+"\n"));
//        out.println(stringBuilder.toString());
        out.flush();
    }

    private static void bucketSort() throws IOException {
        long l = System.currentTimeMillis();
        List<Integer> list = getContext("");
        int[] ints = list.stream().mapToInt(Integer::intValue).toArray();
        bucketSort(ints);
//        print(list);
        System.out.println("bucketsort : "+(System.currentTimeMillis() - l));
    }




    public static void bucketSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < arr.length; i++) {
            max = Math.max(max, arr[i]);
        }
        int[] bucket = new int[max + 1];
        for (int i = 0; i < arr.length; i++) {
            bucket[arr[i]]++;
        }
        int i = 0;
        for (int j = 0; j < bucket.length; j++) {
            while (bucket[j]-- > 0) {
                arr[i++] = j;
            }
        }
    }

    public static void shellSort(int[] array){
        int value = 0;
        int index = 0;
        for (int gap = array.length / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < array.length; i++) {
                index = i;
                value = array[index];
                if (array[index] < array[index - gap]) {
                    while (index > 0 && value < array[i - gap]) {
                        value = array[i - gap];
                        gap--;
                    }
                    array[index] = value;
                }
            }
        }
    }

    private static void radixSort() throws IOException {
        long l = System.currentTimeMillis();
        List<Integer> list = getContext("");
        int[] ints = list.stream().mapToInt(Integer::intValue).toArray();
        Code_07_RadixSort.radixSort(ints);
//        print(list);
        System.out.println("radixSort : "+(System.currentTimeMillis() - l));
    }

    private static void quickSort1() throws IOException {
        long l = System.currentTimeMillis();
        List<Integer> list = getContext("");
        int[] ints = list.stream().mapToInt(Integer::intValue).toArray();
        Code_04_QuickSort.quickSort(ints);
//        print(list);
        System.out.println("quickSort : "+(System.currentTimeMillis() - l));
    }

    private static void mergeSort() throws IOException {
        long l = System.currentTimeMillis();
        List<Integer> list = getContext("");
        int[] ints = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            ints[i] = list.get(i);
        }
        Code_05_MergeSort.mergeSort(ints);
//        print(list);
        System.out.println("mergeSort : "+(System.currentTimeMillis() - l));
    }

    private static void jdkSort() throws IOException {
        long l = System.currentTimeMillis();
        List<Integer> list = getContext("");
        int[] ints = list.stream().mapToInt(Integer::intValue).toArray();
        Arrays.sort(ints);
//        print(list);
        System.out.println("jdkSort : "+(System.currentTimeMillis() - l));
    }

    public static void main(String[] args) throws IOException {
        quickSort1();
        mergeSort();
        radixSort();
        bucketSort();
        jdkSort();
    }
}
